#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/13
# @Author   :Changshu
# @File     :practice_111.py

# 给定一个二叉树，找出其最小深度。
#
# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

class TreeNode:
	def __init__(self,x):
		self.val=x
		self.left=None
		self.right=None

def minDepth(root:TreeNode):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return 1
	maxInt =10**9
	if root.left is not None:
		minDepth=min(minDepth(root.left),maxInt)
	if root.right is not None:
		minDepth=min(minDepth(root.right),maxInt)
	return minDepth+1

if __name__ == '__main__':
	root = TreeNode(3)
	node1_1 = TreeNode(9)
	node1_2 = TreeNode(20)

	root.left = node1_1
	root.right = node1_2

	node2_1 = TreeNode(15)
	node2_2 = TreeNode(7)
	node1_2.left = node2_1
	node1_2.right = node2_2

	r=minDepth(root)
	print(r)